/**
 * @Author：ming
 * @Date：2023/10/21 3:36 AM
 * @Filename：Lc547_Bfs
 */

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ming
 */
public class Lc547_Bfs {
    public int findCircleNum(int[][] isConnected) {
        int cities = isConnected.length;
        boolean[] visit = new boolean[cities];
        Queue<Integer> queue = new LinkedList<>();
        int province = 0;
        for (int i = 0; i < cities; i++) {
            if (!visit[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    visit[j] = true;
                    for (int k = 0; k < cities; k++) {
                        if (isConnected[j][k] == 1 & !visit[k]) {
                            queue.offer(k);
                        }
                    }
                }

                province++;
            }
        }

        return province;
    }
}
